package com.yoso.alg;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.Map;

/**
 * 3. 无重复字符的最长子串
 * @author yoso
 * @date 2024-07-20
 */
class Solution3 {
    @Test
    public void t(){
        String s = "bbbbb";
        int i = lengthOfLongestSubstring(s);
        System.out.println("i = " + i);
    }

    /**
     * @param s
     * @return int
     */
    public int lengthOfLongestSubstring(String s) {
        char[] charArray = s.toCharArray();
        // 最大长度
        int length = 0;
        // 首字符下标
        int start = 0;
        // 尾字符下标
        int end = 0;
        // 记录当前字符串的字符及下标
        Map<Character, Integer> map = new HashMap<>();
        while (end < charArray.length) {
            char rep = charArray[end];
            // 遇到重复字符 && 大于开始字符的下标
            if (map.containsKey(rep) && map.get(rep) >= start) {
                length = Math.max(end - start, length);
                // 更新首字符下标为重复字符的下一个位置
                start = map.get(rep) + 1;
            } else if (end == charArray.length - 1) {
                length = Math.max(end + 1 - start, length);
            }
            map.put(rep, end);
            // 右指针向后移动
            end++;
        }
        return length;
    }


}